package excercise.dynamic;

/**
 * 01背包，物品数量一个，选择或者不选
 */


public class PackProblem {

    public static void solution(int t, int curIdx, int[] costi, int[] vali) {
        // int ans = f(t, 0, costi, vali);
        int ans = f2(t, costi, vali);
        System.out.println("ans = " + ans);

    }

    /**
     * @param t
     * @param curIdx
     * @param costi
     * @param vali
     * @return
     */
    public static int f(int t, int curIdx, int[] costi, int[] vali) {

        if (t <= 0 || curIdx >= costi.length || t < costi[curIdx]) {
            return 0;
        }

        int ans = Math.max(vali[curIdx] + f(t - costi[curIdx], curIdx + 1, costi, vali),
                f(t, curIdx + 1, costi, vali));

        return ans;
    }

    public static int f2(int t, int[] costi, int[] vali) {
        // dp[i][j]: 1~i号物品，容量不超过j的情况下的最大收益
        int[][] dp = new int[costi.length + 1][t + 1];
        int n = costi.length;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];

                if (j >= costi[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], vali[i - 1] + dp[i - 1][j - costi[i - 1]]);
                }
            }
        }
        return dp[costi.length][t];
    }

    public static void main(String[] args) {
        int[] costi = {3, 5, 2, 1, 6};
        int[] vali = {2, 3, 4, 2, 10};
        int t = 10;

        solution(t, t, costi, vali);
    }

}
